package com.tys.algorithm.advanced.code.class17;

import java.util.ArrayList;
import java.util.List;

public class Code04_PrintAllPermutations {
    //打印一个字符串的全部排列
    //方法1：
    public static List<String> permutation1(String s) {
        //结果链表
        List<String> ans = new ArrayList<>();
        //null或0，返回空链表
        if (s == null || s.length() == 0) {
            return ans;
        }
        //s转字符数组
        char[] str = s.toCharArray();
        ArrayList<Character> rest = new ArrayList<Character>();
        //将所有字符放入rest
        for (char cha : str) {
            rest.add(cha);
        }
        String path = "";
        //调用递归
        f(rest, path, ans);
        return ans;
    }

    //rest 剩余字符
    //path 之前的决策
    //ans 结果
    public static void f(ArrayList<Character> rest, String path, List<String> ans) {
        //为空将path加入ans
        if (rest.isEmpty()) {
            ans.add(path);
        } else {
            //总字符数
            int N = rest.size();
            for (int i = 0; i < N; i++) {
                //获取当前字符
                char cur = rest.get(i);
                //从rest中删除当前字符
                rest.remove(i);
                //将当前字符加入path
                f(rest, path + cur, ans);
                //恢复现场：将当前字符加回去
                rest.add(i, cur);
            }
        }
    }

    //打印一个字符串的全部排列
    //方法2：
    public static List<String> permutation2(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        g1(str, 0, ans);
        return ans;
    }

    //结果就在str里面
    public static void g1(char[] str, int index, List<String> ans) {
        //到末尾，交换过程结束：str转字符串放结果
        if (index == str.length) {
            ans.add(String.valueOf(str));
        } else {
            //当前index位置字符
            for (int i = index; i < str.length; i++) {
                //index值和i交换
                swap(str, index, i);
                //跑所有的值
                g1(str, index + 1, ans);
                //换回index和i位置值
                swap(str, index, i);
            }
        }
    }

    //打印一个字符串的全部排列，要求不要出现重复的排列
    public static List<String> permutation3(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        g2(str, 0, ans);
        return ans;
    }

    public static void g2(char[] str, int index, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(str));
        } else {
            //去重
            boolean[] visited = new boolean[256];
            for (int i = index; i < str.length; i++) {
                //去重:i位置没有试过的才试
                if (!visited[str[i]]) {
                    visited[str[i]] = true;
                    swap(str, index, i);
                    g2(str, index + 1, ans);
                    swap(str, index, i);
                }
            }
        }
    }

    public static void swap(char[] chs, int i, int j) {
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
    }

    public static void main(String[] args) {
        String s = "acc";
        List<String> ans1 = permutation1(s);
        for (String str : ans1) {
            System.out.println(str);
        }
        System.out.println("=======");
        List<String> ans2 = permutation2(s);
        for (String str : ans2) {
            System.out.println(str);
        }
        System.out.println("=======");
        List<String> ans3 = permutation3(s);
        for (String str : ans3) {
            System.out.println(str);
        }

    }

}
